package com.cqs.leetcode.dp;

import java.util.PriorityQueue;

public class SuperUglyNumber313 {

    public int nthSuperUglyNumber(int n, int[] primes) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(1);
        while (pq.size() > 0) {
            Integer poll = pq.poll();
            if (--n == 0) {
                return poll;
            }
            for (int p : primes) {
                if (Integer.MAX_VALUE / poll >= p) {
                    pq.add(poll * p);
                }
                // 避免重复的元素进入
                if (poll % p == 0) {
                    break;
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(6 % 3);
        SuperUglyNumber313 s = new SuperUglyNumber313();
        System.out.println(s.nthSuperUglyNumber(12, new int[]{2,7,13,19}));
        System.out.println(s.nthSuperUglyNumber(100000, new int[]{7,19,29,37,41,47,53,59,61,79,83,89,101,103,109,127,131,137,139,157,167,179,181,199,211,229,233,239,241,251}));
    }
}
